package com.lsa.letcode.the90.subsets2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Solution {
	 public List<List<Integer>> subsetsWithDup(int[] nums) {
		 	List<List<Integer>> subsets = new ArrayList<List<Integer>>();
		 	if (nums == null || nums.length == 0) {
		 		subsets.add(new ArrayList<Integer>());
		 		return subsets;
		 	}
	        Arrays.sort(nums);
	        Combination c = new Combination(nums);
	        long[] pVal = new long[1];
	        do{
	        	List<Integer> digits = c.asList(pVal);
				subsets.add(new CombinationDigits(digits, pVal[0]));
	        }
	        while(c.next());
	        
	        Collections.sort(subsets, new Comparator<List<Integer>>(){
				@Override
				public int compare(List<Integer> l1, List<Integer> l2) {
					CombinationDigits cd1 = (CombinationDigits)l1;
					CombinationDigits cd2 = (CombinationDigits)l2;
					long res = cd1.value - cd2.value;
					if (res > 0){
						return 1;
					} 
					else if (res < 0){
						return -1;
					}
					else {
						return 0;
					}
				}
	        	
	        });
	        
	        List<List<Integer>> res = uniq(subsets);
			return res;
	    }
	    
	    static List<List<Integer>> uniq(List<List<Integer>> l) {
	    	if (l.size() < 2) {
	    		return l;
	    	}
	    	
	    	CombinationDigits prev = (CombinationDigits) l.get(0);
			int pos = 0;
			
			for (int i = 1; i < l.size(); i++) {
				CombinationDigits n = (CombinationDigits) l.get(i);
				if (prev.value != n.value) {
					l.set(++pos, n);
					prev = n;
				}
			}
			
			return l.subList(0, pos + 1);
	    }
	 
	 	@SuppressWarnings("serial")
		private static class CombinationDigits extends ArrayList<Integer>{
	 		private final long value;
	 		
			public CombinationDigits(List<Integer> digits, long value) {
				super(digits);
				this.value = value;
				
			}
	 	}
	 	
	 	static long value(int[] bits) {
	 		long val = 0;
	 		int mask = 1;
	 		for (int i = bits.length - 1; i > -1; i--) {
	 			if (bits[i] != 0) {
	 				val += mask; 
	 			}
	 			mask <<= 1;
	 		}
	 		return val;
	 	}
	    
	    static class Combination {
	    	int[] bits;
			private int[] ints;
	    	
	    	Combination(int[] ints) {
	    		bits = new int[ints.length];
	    		this.ints = ints;
	    	}
	    	
	    	
	    	List<Integer> asList(long[] pVal){
	    		List<Integer> l = new ArrayList<Integer>();

	    		long val = 0;
	    		long mask = 1;
	    		for (int i = 0; i < bits.length; i++) {
					if (bits[i] != 0) {
						l.add(ints[i]);
						val += mask;
					}
					mask <<= 1;
				}
	    		
	    		pVal[0] = val;
	    		
	    		return l;
	    	}
	    	
	    	void flip(int i, int bit) {
	    		bits[i] = bit;
	    	}
	    	
	    	boolean next(){
	    		if (bits.length == 0) {
	    			return false;
	    		}
	    		int carry = 0;
	        	for (int i = bits.length - 1; i > -1; i--) {
	    			int d = bits[i] + carry + (i == bits.length - 1? 1 : 0);
	    			carry = d / 2;
	    			d = d % 2;
	    			flip(i, d);
	    		}
	    		return carry == 0;
	    	}
	    }
}